Field of the Invention
The invention relates to the field of network communication technology, and more particularly to a method of aggregation of source address bunches and a network routing system.
Description of the Related Art
IP network is the infrastructure of Internet communications, and packet switching and routing are two core elements of an IP network. The exponential increase of the amount of hosts and subnets on the Internet with time, the use of unrelated addresses of the provider by customer network, the deployment of traffic engineering, multi-host connection and many other factors are making the IP network routing system face unprecedented scalability challenges.
In the past two decades, the size of the Internet has increased over time, approximately being exponential growth model, which can be seen from the exponential increase of the amount of hosts and subnets on the Internet.
Data show that there are nearly billions of hosts on the Internet, while the size of autonomous domain (i.e. AS), the number of autonomous domains and the number of connections to the Internet of each AS on the Internet, are also increasing rapidly.
One of the direct consequences of the rapid increase of internet is that the amount of inter-domain routing states established and maintained by inter-domain routing systems is increasing fast, which causes the subnet to expand its own address capacity by adding new prefix, while the increase of the number of subnets directly contributes to the increase of routing table entries of global routing nodes.
The direct consequence of the increased number of internet global routing table is that the number of routing states preserved and maintained by intra-domain and inter-domain routing nodes approaches to exponential increase, that is, the number of routing table entry of routing nodes increases exponentially. Such an increase directly leads to the huge storage overhead and processing overhead in processing routing tables, a low efficiency in packet forwarding, slow convergence speed of routing calculation, more power and cost consumption required for processing, etc. In addition, the large amount of global routing table entry also implies the need for more routes advertised by routing protocols, the direct consequence of which is the instability of the global routing protocol.
Network routing scalability indicates that the speed of increase of routing states of each routing node in the network routing system is less than the speed of increase of the connected hosts, subnets, and the total routing nodes. For example, when the number of hosts or subnets increases near-exponentially along with time, the amount of routing state of routing node increases linearly along with time. IP network routing system usually establishes routing information for each host and subnet with a public IP address. An effective way to solve the scalability issue is to constitute address aggregation. The core of address aggregation technology is making multiple routing states present as a single through the format of compression, whereby forming a scalable network in general. Currently, the only available address aggregation technique for Internet routing system is CIDR (Classless Inter-Domain Routing). The essence of CIDR is: based on the variable-length mask VLSM (Variable Length Subnet Mask) technology, making multiple smaller addresses prefixes which represent like a numerically “continuous (power of 2)” aggregated into a single large address prefixes. From the perspective of the network topology, with the corresponding address assignment method, CIDR abandoned the classification according to IP address structure (before CIDR occur, IP addresses are divided into five categories, A, B, C, D and E), and combine the multiple small networks corresponding to multiple contiguous blocks of IP addresses into a single large network, forming the so-called “super-network.” On the other hand, from the perspective of network routing, since the number of routes is less after combining the routing table entries into a fewer entries, thus CIDR effectively reduces the number of routing entries that must be saved in the routing table. To the routing protocols, CIDR also reduces the number of routing advertisement that must be published and updated.
Twenty years ago, CIDR did reduce the number of routing entries in the routing table, but the fact that the routing table entries of routing node has increased near-exponentially in recent years. Today, Internet has been gone far beyond the capacity of aggregation of CIDR in size, speed, address, usage patterns, and many others. Since the scalability issue, especially solving the routing inter-domain routing has reached a critical state, in October 2006, the Internet Architecture Board IAB in IETF (Internet Architecture Board) held a special working conference for routing and addressing, RAWS (Amsterdam IAB Routing and Addressing Workshop) in Amsterdam, where the routing scalability was rated as a top issue to show the highest focus on it. The meeting drew the following conclusions: as the wide use of network multi-homing, traffic engineering and other technology, the number of Internet routing is growing rapidly and its speed is faster than Moore's Law curve. Although advances in hardware technology can support the sustained growth of routing tables in a given period, but the deep-seated problems such as routing instability is difficult to be solved through hardware technology. In addition, it will take many years for the mature of the new routing and addressing architecture technology and deployment, so we need to start research in this area as early as possible.
On the basis of consensus on the issue of the scalability of the Internet routing, the international academia and industry have done a lot of research and tried to put forward a number of solutions and programs and summed up in three categories as “PI elimination”, “spatial separation” and “location”.
Firstly, PI elimination method (Elimination). This method encourages or requires the network of the customer and service provider not to use non-aggregated “independent provider address (PI address)”, and only use “address assigned by the provider” (i.e. PA address) obtained from a provider, which can be aggregated. The essence of PI eliminating method is still focusing on the maintenance of validity of CIDR “continuous addresses convergence”, and the cost is completely sacrificing the flexibility of customers to choose service provider, and thus unable to adapt to the natural evolution of the Internet.
To strengthen the effects of convergence of the IPv4 CIDR address of PA types, a typical practice is that the regional address allocation mechanism RIR (including RIPE NCC, AfriNIC, APNIC, ARIN, and LACNIC) defined minimum size of address block allocated for users as “.*.*.*.*/21”, while the introduction of the corresponding filtering mechanism in routing protocols allows routing entity to refuse routing announcements for address prefix size smaller than “.*.*.*.*/21”. For IPv6, the minimum size of allocated address block is limited to “.*:*:*:*:*:*:*:*/32”.
Secondly, the spatial separation (Separation). The method separates the network portions with two different types of PA and PI address. In particular, the local or the edge of the network can use PI addresses for local routing, while the global routing system of network will use aggregated PA address for the global routing. Setting “address space mapping” mechanism at the connection of the network portion of two different addresses of PA and PI to perform an interconnection between corresponding networks of different part of address space. The direct benefits of spatial separation method is to make the local/edge routing state of network portion of PI address space hidden to the network portion of the PA address space, and thus this directly reduces the number of global routing state of PA network portion of the address space needed to be built and maintained. The negative side of the separation method is that the introduction of the “address space mapping” increases the complexity of the network structure itself, maintenance overhead and communication overhead. It is worth noting that the essence of this method is to reduce the overall number of global routing state needed to be established and maintained rather than a true address aggregation method.
Thirdly, location-based routing. Unlike other methods, this method does not use the network address of the network node, but it uses its location for routing. In the routing system based on geographic location, the network node is assigned with its own location. When the network node 1 sends data to the network node 2, the network node 1 also needs to know where the network location of the current node 2. A network node obtains the location information of other network nodes through internal searching process or external location service. A typical application scenarios for location-based routing method is wireless network environment, which is characterized as follows: firstly, establishment of the route is no longer related with the network topology but the image (or projector) of network topology on geographic map; secondly, the manifestations of routing system scalability change from the complexity of routing table to the complexity of obtaining the service of the node location information; thirdly, the degree of difficulty and complexity of obtaining network node location information are determined by the particle size of location information of the network node and the level of aggregation, in other words, location-based routing method does not solve the scalability problem, but also faces the same scalability issue as the non-location-based routing method essentially in a different form.
It is noted that, in addition to location-based routing, the above methods, which aim at improving the routing scalability of the Internet and use CIDR as a fundamental method for address aggregation without exception, in other words, they are all high-level systems approaches based on the fundamental method. However, from a scalability perspective, CIDR does not have the natural adaptability of the increasing size of hosts, networks of customers and service providers, and the main reason is as follows.
Firstly, CIDR does not have the natural adaptability for the evolution of address assignment of the customer or service provider network. As a core feature of CIDR, focusing on “aggregation of continuous numerical prefix” means CIDR cannot realize the aggregation of several “non-numerical continuous” address prefix. Therefore, for an address allocation institution, CIDR means it can get a good address aggregation effect only if it takes full account of “continuity” of address assignment of the customer or service provider network. The limit brings a significant challenge to the address allocation mechanism, because the size of a client or service provider network usually changes dynamically over time (e.g., expanding), while the customer or service provider usually applies the scale of the size of the address space (someone may consider certain margin) only in accordance with the size of certain network period. Once address allocation mechanism assigns address for a client or service provider's network, it is difficult to predict the address space to which the customer or the service provider's network apply next time, and it is also difficult to set aside “continuous” new address space for them. A typical address allocation strategy taken by Internet regional registries RIR (Regional Internet Registry) is: reserve continuous address space for a subsequent allocation so that the address can continue to be aggregated. Obviously, this strategy reduces the efficient use of address space. Because even we reserve continuous address space, it is difficult to estimate the size of the amount set aside. In short, it is difficult for the address allocation mechanism to ensure the “continuity” of the assigned address for the same customer or service provider's network two or more times, which makes the “continuity” of address aggregation imposed by CIDR and the “discontinuity” of actual address assignment constitutes a pair of irreconcilable contradictions.
Secondly, CIDR does not support the flexibility on the selection of service provider for customers. In order to achieve aggregation of addresses, CIDR must also be based on the address allocation scheme of ISP (Internet Service Provider), and use the so-called address scheme “assigned by providers” (corresponding addresses are called “PA address”, Provider Assigned Addresses), that is, customers get their own address from their Service Providers. Thus, from the perspective of the address space, customers' address space is a subset of the address space of the service provider. The advantage of PA address scheme is to ensure the aggregation of continuous addresses, but its obvious disadvantage is that it limits the choice and change customer make to the service provider. For example, when customer networks change their service provider because of service, price, performance, reliability, and other purposes, they need to reconfigure the IP address of all the hosts and network devices of the customer network, that is, they apply for a new address space from their new service provider first, then they configure new address for all hosts and network devices. But the configuration of new addresses for the host and network device may mean a re-configuration or modification of some or all applications running on top of the customer's network, which is called the problem of change the address (Renumbering). A large amount of money, manpower and time costs are required to change the address. And today, customers hope to have sufficient flexibility to choose and change their network service provider and avoid changing their original addresses.
In short, the feature of “continuous aggregation” allows CIDR to aggregate a plurality of numerically discontinuous address prefixes belonging to the same AS into a single prefix. And this feature is an important reason that there is a huge number of routing table entries which are growing rapidly. Thus, CIDR is no longer suitable as an approach based on address aggregation. The invention provides a new method based on address aggregation, i.e., “source address aggregation”, which can aggregate plurality of numerically discontinuous address prefix belonging to a single converging AS into a single address prefix.